1. Field of the Invention
The invention relates to an encoding/decoding device for transforming data that includes of a plurality of coefficients continuously concatenated into a variable length code.
2. Description of the Related Art
In the electronic media device industry, which includes facsimile machines and remote telecommunication conference systems which transform image data into digital information by sampling and transmitting it to a remote location, the demand for improved image quality is continually increasing. For example. certain binary monochrome images have been enhanced to multiple gray-scale images, and more recently to color images.
Generally, the quantity of information in image data is very large, particularly, in multiple gray-scale Image data and color image data. For this reason, when image data is transmitted to a remote location and is saved, a data compression technique is used for compressing the image data.
For example, it is possible to compress the quantity of information with little or no degradation of image quality so that any degradation is unidentifiable to the human eye by deleting the high-frequency component of the image data which human eyes can barely identify. Thus. the image data is compressed by deleting the high-frequency component which cannot be detected by the human eye.
One data compression technique of this type is the JPEG (Joint Photographic Experts Group) algorithm which is n international standard coding method for color still images. As shown In FIG. 3. in the DCT (Discrete Cosine Transform) method of the JPEG algorithm. encoding and decoding of image data is performed by a block by dividing original image data into blocks, each of which includes 8 horizontal pixel .times.8 vertical pixels. Thus, the encoding and decoding of image data is performed by a block composed of 64 pixels.
First, encoding of the original image data is performed with a data encoder 34. In the data encoder 34, a DCT circuit 36 performs the discrete cosine transform for each pixel value of each block. and thereafter. a quantization circuit 38 quantizes the transformed block on the basis of a quantization table 40. Then, an entropy coding circuit 42 performs, for example, Huffman coding to the quantized block for compression based of a coding table 44. The original image data variable-length coded in this manner is transmitted. for example. via a transmission line.
In contrast, decoding of the original image data is performed with a data decoder 46. In the data decoder 46, an entropy decoding circuit 48 performs Huffman decoding for each pixel value of each block, which is variable-length coded and is made to be a data stream, using the coding table 44, which is the same table utilized for encoding. Next, an inverse quantization circuit 50 performs inverse quantization to the decoded values using the quantization table 40, which is the same table utilized for quantizing. After that. an inverse DCT circuit 52 performs the inverse discrete cosine transform for decompression, and a decoded image data is obtained.
Here, among the 64 coefficients obtained by performing the DCT transform for a block of 8 horizontal pixels (X=0-7).times.8 vertical pixels (Y=0-7), that is, 64 pixels (PXY). the coefficient S.sub.00 is called a DC component, and the residual sixty-three coefficients are called AC components. The DC component shows an average value (a direct-current component) of the sixty-four pixels. In Huffman coding/decoding, encoding and decoding are different than the DC component and AC components. respectively.
For example, In Huffman coding, encoding of AC coefficients Is performed by performing zigzag-scanning to quantized data, thereafter obtaining a run length (NNNN) representing a count of coefficients having continuous zeros, and obtaining a group number (SSSS) of the AC coefficients from the values of the AC coefficients that follow zero but are not zero. Further, encoding of the AC coefficients is performed by assigning a code word, each having a code length of one to sixteen bits, according to the run length and group number NNNN/SSSS, and adding additional bits, from 0 bit to 15 bits, to this code word according to the group number.
Here, by illustrating Huffman coding of the JPEG, conventional encoding methods and associated problems are described.
In conventional encoding methods, a memory having a total of twenty bits length and storing a 16-bit code CODE representing each code word, and a 4-bit size SIZE representing code length of each code word in each address is provided for all code words to be encoded. Further, the code CODE and size SIZE, which are stored In the memory, are read and the code CODE whose bit length is equal to the number of bits designated with the size SIZE is used.
For example, if a run length and a group number NNNN/SSSS are 0/4, the code word is "1011" (a binary number; hereinafter, this notation is similarly treated) according to a luminance table recommended by the JPEG and its code length is 4 bits. In this case, the following twenty-bit data is read as the code CODE and size SIZE from the memory.
Code CODE="0000 0000 0000 1011" PA1 Size SIZE="0011" PA1 Size SIZE="0011" PA1 Offset OFFSET="0000 0001" PA1 Base BASE="0000 0000 0000 1010"
Here, since sixteen types of code lengths that are 1-16 bits of a code word are represented in 4 bits from "0000" to "1111", the size SIZE is not "0100", but "0011". In addition, only the low-order 4-bit data="1011", which Is designated by the size SIZE="0011", in the code CODE="0000 0000 0000 1011" is used as a code word corresponding to the run length and group number NNNN/SSSS=0/4.
This method has the advantage that it is possible to obtain the code CODE and size SIZE of the code word corresponding to the run length and group number NNNN/SSSS=0/4 by only reading data from the memory once, and hence, encoding the data at high-speed. However, this is problematic because 20-bit data memory storing is necessary in each address, the bit length of the memory becomes large, and hence, a large memory area is required.
In another conventional encoding method, each minimum value in code words having code lengths of one to sixteen bits is defined as a base BASE and is stored in each address of the memory having a 16-bit length. Further, with regard to all code words to be encoded, 4 bits of size SIZE representing a code length of each code word and 8 bits of offset OFFSET representing the numerical difference between a base BASE corresponding to this size SIZE and each code word, that is, 12 bits of data are stored in each address of the memory aside from the 16-bit memory address.
In this method, first, a total twelve bits of size SIZE and offset OFFSET, which are stored in an address designated by the run length and group number NNNN/SSSS, are read. After 16-bits of base BASE stored in an address designated by the size SIZE is read in the next cycle, a code CODE is calculated by adding the offset OFFSET to the base BASE. A bit count of the code CODE to be used is 5 designated by the size SIZE.
Similarly, assuming that the run length and group number NNNN/SSSS=0/4, first, the following twelve bits of data are read from the memory as the size SIZE and offset OFFSET.
Subsequently. with using the size SIZE="0011"read from the memory as an address, the following 16-bits of base BASE are read from the memory.
Then, the code CODE="0000 0000 0000 1011" is obtained by adding the base BASE="0000 0000 0000 1010" and the offset OFFSET "0000 0001". Only the low-order 4-bit data="1011", which is designated by the size SIZE="0011", In the code CODE="0000 0000 0000 1011" is used as a code word corresponding to the run length and group number NNNN/SSSS=0/4.
This method has the advantage that. since a memory capable of storing at most sixteen-bit data in each address can be used. it is possible to use a memory having small bit length. However, this is problematic because the data must be read twice from the memory, which slows processing. In addition, if another memory Is used as the memory for storing the base BASE, this causes the additional problem of an increased number of memories which increases memory area.